package com.lzhsite.leetcode.algoritom.practise.arrays.dictorder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

/*
给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例 1：

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

*/
public class 字典序问题 {

	class Node {
		public String key;
		public int value;

		public Node(String key, int value) {
			super();
			this.key = key;
			this.value = value;
		}

	}

	public List<String> topKFrequent(String[] words, int k) {

		ArrayList<String> result = new ArrayList<String>();
		Map<String, Integer> map = new HashMap();
		for (int i = 0; i < words.length; i++) {
			if (map.get(words[i]) == null) {
				map.put(words[i], 1);
			} else {
				map.put(words[i], map.get(words[i]) + 1);
			}
		}
		ArrayList<Node> list = new ArrayList<Node>();
		Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
		while (it.hasNext()) {
			Map.Entry<String, Integer> entry = it.next();
			Node node = new Node(entry.getKey(), entry.getValue());
			list.add(node);
		}
		Collections.sort(list, new Comparator<Node>() {
			@Override
			public int compare(Node o1, Node o2) {
				// TODO Auto-generated method stub
				return (o2.value - o1.value) == 0 ? (o1.key.compareTo(o2.key)) : (o2.value - o1.value);
			}
		});
		for (int i = 0; i < k; i++) {
			Node node = list.get(i);
			result.add(node.key);
		}
		return result;
	}

	public static void main(String[] args) {

		String[] arr = { "i", "love", "leetcode", "i", "love", "coding" };
		List<String> result = new 字典序问题().topKFrequent(arr, 2);
		for (String s : result) {
			System.out.print(s+" ");
		}
	 
	}
}
